package leetcode_800;

/**
 *@author 周杨
 *MyCalendarI_729 日历的填入 
 *describe:其实也就是区间的重叠和去重问题 用线段树解决 AC 71%
 *2018年10月13日 下午9:48:00
 */
public class MyCalendarI_729 {
	
	public static void main(String[] args) {
		MyCalendarI_729 test=new MyCalendarI_729();
		System.out.println(test.book(33, 51));
		System.out.println(test.book(19, 30));
		System.out.println(test.book(19, 30));
		
	}
	
	static class LinerTree{
		int start;
		int end;
		LinerTree left;
		LinerTree right;
		public LinerTree(int start,int end) {
			this.start=start;
			this.end=end;
		}
	}
	LinerTree root=null;
	public MyCalendarI_729() {
        
    }
    
    public boolean book(int start, int end) {
        if(root==null) {//根节点
        	LinerTree node=new LinerTree(start, end-1);
        	this.root=node;
        	return true;
        }
        else {
        	//因为有两种可能 1是找到了插入点 2是没有找到插入点 这两种情况都要返回节点
        	//那么自行判断 返回的节点是否是插入点 
        	LinerTree leftNode=help(root,start);
        	if(start<=(leftNode.end)&&start>=(leftNode.start))
        		return false;
        	LinerTree rightNode=help(root,end-1);
        	if(end-1<=rightNode.end&&end-1>=rightNode.start)
        		return false;
        	//开始插入 先找插入点
        	if(leftNode!=rightNode) {
        		return false;//插入点不唯一 那么结束
        	}
        	if(start<=leftNode.start&&end-1>=leftNode.end) {//整体包含
        		return false;
        	}
        	LinerTree next=new LinerTree(start, end-1);
        	if(end>leftNode.end) {
        		leftNode.right=next;
        	}
        	else {
        		leftNode.left=next;
        	}
        }
        return true;
    }
    
    public LinerTree help(LinerTree root,int val) {
    	if(root.start>val) {//超过了
    		if(root.left==null) {
    			return root;
    		}
    		return help(root.left,val);
    	}
    	else if(root.end<val) {
    		if(root.right==null)
    			return root;
    		return help(root.right,val);
    	}
    	else {
    		return root;//错了
    	}
    }

}
